Lần đào thoát đầu tiên xảy ra khi Douglass ở dưới tay Freeland, nhưng không thành công. Đến năm 1836, cậu cố trốn khỏi Covey nhưng lại thất bại. Năm sau, Douglass gặp gỡ và đem lòng yêu Anna Murray, một phụ nữ da đen tự do sống ở Baltimore, lớn hơn cậu năm tuổi. Chính tư cách một người tự do của Murray củng cố niềm tin của Douglass rằng một ngày nào đó cậu sẽ giành được tự do.[10]

Ngày 3 tháng 9 năm 1838, Douglass lên một chuyến xe lửa tiến về hướng Bắc. Cậu nhảy lên một toa tàu tại một địa điểm gần kho hàng của công ty hỏa xa Philadelphia, Wilmington & Baltimore, tọa lạc trong khu dân cư Canton ở đường President and Fleet, phía đông cảng Baltimore thuộc nhánh Bắc của Sông Patapsco. (Sau này nhà kho trở thành nhà ga Đường President, xây dựng năm 1849-50; nó từng được biết đến là địa điểm đào thoát của nhiều nô lệ, là một phần trong nhiều lộ trình thuộc "Đường Hỏa xa ngầm" rất nổi tiếng giúp nhiều nô lệ trốn thoát trong thời gian xảy ra cuộc Nội chiến.)

Chàng thanh niên Douglass đặt chân đến Havre de Grace thuộc Hạt Harford, Maryland. Thị trấn này nằm cạnh con sông Susquehanna chạy dọc theo ranh giới với Pennsylvania rồi đổ vào Vịnh Chesapeake. Murray mang đến cho Douglass một bộ đồng phục thủy thủ cùng một phần trích từ số tiền tiết kiệm của cô để trả tiền cho chuyến đi. Douglass cũng kiếm được giấy tờ tùy thân nhờ một thủy thủ da đen.[10][12][13] Douglass lên một chuyến phà hơi nước băng qua sông Susquehanna đến Hạt Cecil, rồi lên tàu đi tiếp đến Wilmington, Delaware, cảng biển lớn tọa lạc ở đầu Vịnh Delaware. Từ đây, do hết đường xe hỏa, cậu phải đi thuyền hơi nước xuôi dòng sông Delaware hướng về phía bắc đến "Thành phố Quaker" ở Philadelphia, Pennsylvania, thành lũy của phong trào chống nô lệ, rồi đến ngôi nhà an toàn của một người hoạt động giải phóng nô lệ nổi tiếng, David Ruggles, ở Thành phố New York. Toàn bộ hành trình kéo dài gần 24 giờ.[14]

Ngay sau khi đến nơi, Douglass báo tin cho Murray để đến với cậu ở New York. Ngày 15 tháng 9 năm 1838, một mục sư Trưởng Lão người da đen cử hành hôn lễ cho hai người.[10][14] Họ phải sử dụng tên Johnson để tránh bị theo dõi.[10]